#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

// 二叉树节点定义
struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

/**
 * 序列化二叉树为字符串
 * @param root: 二叉树根节点
 * @return: 序列化后的字符串（LeetCode格式）
 */
char *serialize(struct TreeNode *root)
{
    //======Begin======
    if (root == NULL)
    {
        char *res = (char *)malloc(3);
        strcpy(res, "[]");
        return res;
    }

    // 动态分配队列
    struct TreeNode **queue = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * 10000);
    int front = 0, rear = 0;
    queue[rear++] = root;

    // 动态数组存储节点字符串
    char **arr = (char **)malloc(sizeof(char *) * 10000);
    int arr_index = 0;

    while (front < rear)
    {
        struct TreeNode *cur = queue[front++];
        if (cur != NULL)
        {
            // 非空节点：记录值，并加入子节点
            char *temp = (char *)malloc(12);
            sprintf(temp, "%d", cur->val);
            arr[arr_index++] = temp;
            queue[rear++] = cur->left;
            queue[rear++] = cur->right;
        }
        else
        {
            // 空节点：记录"null"
            char *null_str = (char *)malloc(5);
            strcpy(null_str, "null");
            arr[arr_index++] = null_str;
        }
    }

    // 移除末尾连续的"null"
    while (arr_index > 0 && strcmp(arr[arr_index - 1], "null") == 0)
    {
        free(arr[arr_index - 1]);
        arr_index--;
    }

    // 计算总字符串长度
    int total_len = 2; // 方括号
    for (int i = 0; i < arr_index; i++)
    {
        total_len += strlen(arr[i]);
        if (i < arr_index - 1)
            total_len++; // 逗号
    }
    total_len++; // 结束符

    // 构建结果字符串
    char *res = (char *)malloc(total_len);
    int pos = 0;
    res[pos++] = '[';
    for (int i = 0; i < arr_index; i++)
    {
        if (i > 0)
            res[pos++] = ',';
        int len = strlen(arr[i]);
        strcpy(res + pos, arr[i]);
        pos += len;
        free(arr[i]); // 释放临时字符串
    }
    res[pos++] = ']';
    res[pos] = '\0';

    // 释放动态分配的内存
    free(arr);
    free(queue);
    return res;
    //=======End=======
}

/**
 * 反序列化字符串为二叉树
 * @param data: 序列化后的字符串（LeetCode格式）
 * @return: 二叉树根节点
 */
struct TreeNode *deserialize(char *data)
{
    //======Begin======
    int len = strlen(data);
    if (len <= 2 || strcmp(data, "[]") == 0)
        return NULL;

    // 复制并处理字符串（去掉方括号）
    char *str = (char *)malloc(len - 1);
    strncpy(str, data + 1, len - 2);
    str[len - 2] = '\0';

    // 分割字符串
    char **tokens = (char **)malloc(sizeof(char *) * 10000);
    int token_count = 0;
    char *token = strtok(str, ",");
    while (token != NULL)
    {
        tokens[token_count++] = token;
        token = strtok(NULL, ",");
    }

    // 创建根节点
    struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    root->val = atoi(tokens[0]);
    root->left = root->right = NULL;

    // 使用队列重建树
    struct TreeNode **queue = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * 10000);
    int front = 0, rear = 0;
    queue[rear++] = root;
    int index = 1; // 当前处理的token索引

    while (front < rear && index < token_count)
    {
        struct TreeNode *cur = queue[front++];

        // 处理左子节点
        if (index < token_count && strcmp(tokens[index], "null") != 0)
        {
            struct TreeNode *left = (struct TreeNode *)malloc(sizeof(struct TreeNode));
            left->val = atoi(tokens[index]);
            left->left = left->right = NULL;
            cur->left = left;
            queue[rear++] = left;
        }
        index++;

        // 处理右子节点
        if (index < token_count && strcmp(tokens[index], "null") != 0)
        {
            struct TreeNode *right = (struct TreeNode *)malloc(sizeof(struct TreeNode));
            right->val = atoi(tokens[index]);
            right->left = right->right = NULL;
            cur->right = right;
            queue[rear++] = right;
        }
        index++;
    }

    // 释放动态分配的内存
    free(str);
    free(tokens);
    free(queue);
    return root;
    //=======End=======
}